Kernel: .venv
MINIMUM EXACT COVER / Покрытие множеств минимальным объемом
In [1]:
Постановка задачи
Представим, что мы имеем конечное множество «U» (universum) и «S» — список подмножеств множества «U».
Покрытием называют семейство наименьшей мощности, объединением которых является . В случае постановки вопроса о разрешении на вход подаётся пара и целое число k; вопросом является существование покрывающего множества мощности k (или менее).
Оптимизационная версия задачи, '''минимальное покрытие множеств''', задаёт вопрос о минимальном объеме покрытия, измеряемого не в числе множеств из «S» покрывающих «U», а в числе элементов в этих подмножествах
In [2]:
In [3]:
Реализация в Pyomo
In [4]:
In [41]:
['C_{0}', 'C_{1}', 'G0', 'G1', 'G2', 'x_{1}', 'x_{2}', 'x_{3}']
In [42]:
[{'C_{0}', 'G1', 'x_{1}'},
{'C_{1}', 'G1', 'x_{1}'},
{'C_{0}', 'C_{1}', 'x_{2}'},
{'G1', 'G2', 'x_{2}'},
{'C_{0}', 'C_{1}', 'x_{3}'},
{'G1', 'G2', 'x_{3}'},
{'G0', 'G1', 'G2'}]
In [43]:
2 Set Declarations
x_index : Size=1, Index=None, Ordered=Insertion
Key : Dimen : Domain : Size : Members
None : 1 : Any : 7 : {0, 1, 2, 3, 4, 5, 6}
каждый_элемент_покрыт_хотябы_одним_множеством_index : Size=1, Index=None, Ordered=Insertion
Key : Dimen : Domain : Size : Members
None : 1 : Any : 8 : {'C_{0}', 'C_{1}', 'G0', 'G1', 'G2', 'x_{1}', 'x_{2}', 'x_{3}'}
1 Var Declarations
x : Size=7, Index=x_index
Key : Lower : Value : Upper : Fixed : Stale : Domain
0 : 0 : None : 1 : False : True : Binary
1 : 0 : None : 1 : False : True : Binary
2 : 0 : None : 1 : False : True : Binary
3 : 0 : None : 1 : False : True : Binary
4 : 0 : None : 1 : False : True : Binary
5 : 0 : None : 1 : False : True : Binary
6 : 0 : None : 1 : False : True : Binary
1 Objective Declarations
set_count : Size=1, Index=None, Active=True
Key : Active : Sense : Expression
None : True : minimize : 3*x[0] + 3*x[1] + 3*x[2] + 3*x[3] + 3*x[4] + 3*x[5] + 3*x[6]
1 Constraint Declarations
каждый_элемент_покрыт_хотябы_одним_множеством : Size=8, Index=каждый_элемент_покрыт_хотябы_одним_множеством_index, Active=True
Key : Lower : Body : Upper : Active
C_{0} : 1.0 : x[0] + x[2] + x[4] : +Inf : True
C_{1} : 1.0 : x[1] + x[2] + x[4] : +Inf : True
G0 : 1.0 : x[6] : +Inf : True
G1 : 1.0 : x[0] + x[1] + x[3] + x[5] + x[6] : +Inf : True
G2 : 1.0 : x[3] + x[5] + x[6] : +Inf : True
x_{1} : 1.0 : x[0] + x[1] : +Inf : True
x_{2} : 1.0 : x[2] + x[3] : +Inf : True
x_{3} : 1.0 : x[4] + x[5] : +Inf : True
5 Declarations: x_index x set_count каждый_элемент_покрыт_хотябы_одним_множеством_index каждый_элемент_покрыт_хотябы_одним_множеством
In [44]:
# ==========================================================
# = Solver Results =
# ==========================================================
# ----------------------------------------------------------
# Problem Information
# ----------------------------------------------------------
Problem:
- Name: unknown
Lower bound: 12.0
Upper bound: 12.0
Number of objectives: 1
Number of constraints: 5
Number of variables: 6
Number of binary variables: 7
Number of integer variables: 7
Number of nonzeros: 6
Sense: minimize
# ----------------------------------------------------------
# Solver Information
# ----------------------------------------------------------
Solver:
- Status: ok
User time: -1.0
System time: 0.02
Wallclock time: 0.02
Termination condition: optimal
Termination message: Model was solved to optimality (subject to tolerances), and an optimal solution is available.
Statistics:
Branch and bound:
Number of bounded subproblems: 0
Number of created subproblems: 0
Black box:
Number of iterations: 0
Error rc: 0
Time: 0.12440919876098633
# ----------------------------------------------------------
# Solution Information
# ----------------------------------------------------------
Solution:
- number of solutions: 0
number of solutions displayed: 0
x[0] 1.0
x[3] 1.0
x[4] 1.0
x[6] 1.0
In [45]:
x[0] 1.0
x[3] 1.0
x[4] 1.0
x[6] 1.0
In [46]:
[0, 3, 4, 6]
In [47]:
In [11]:
[(-3, 1, -2)]
In [12]:
True
In [13]:
[-1, -2, -3]
In [14]:
[(-3, 1, -2)]
In [15]:
In [16]:
[(-1, 3, -2)]
In [17]:
{'G': ['G0', 'G1'],
'x_{1}=0': ['x_{1}', 'C_{0}'],
'x_{1}=1': ['x_{1}', 'G1'],
'x_{2}=0': ['x_{2}', 'C_{0}'],
'x_{2}=1': ['x_{2}', 'G1'],
'x_{3}=0': ['x_{3}', 'G1'],
'x_{3}=1': ['x_{3}', 'C_{0}']}
In [18]:
In [19]:
(['C_{0}', 'G0', 'G1', 'x_{1}', 'x_{2}', 'x_{3}'],
[{'C_{0}', 'x_{1}'},
{'G1', 'x_{1}'},
{'C_{0}', 'x_{2}'},
{'G1', 'x_{2}'},
{'G1', 'x_{3}'},
{'C_{0}', 'x_{3}'},
{'G0', 'G1'}])
In [20]:
# ==========================================================
# = Solver Results =
# ==========================================================
# ----------------------------------------------------------
# Problem Information
# ----------------------------------------------------------
Problem:
- Name: unknown
Lower bound: 8.0
Upper bound: 8.0
Number of objectives: 1
Number of constraints: 4
Number of variables: 6
Number of binary variables: 7
Number of integer variables: 7
Number of nonzeros: 6
Sense: minimize
# ----------------------------------------------------------
# Solver Information
# ----------------------------------------------------------
Solver:
- Status: ok
User time: -1.0
System time: 0.01
Wallclock time: 0.01
Termination condition: optimal
Termination message: Model was solved to optimality (subject to tolerances), and an optimal solution is available.
Statistics:
Branch and bound:
Number of bounded subproblems: 0
Number of created subproblems: 0
Black box:
Number of iterations: 0
Error rc: 0
Time: 0.08855152130126953
# ----------------------------------------------------------
# Solution Information
# ----------------------------------------------------------
Solution:
- number of solutions: 0
number of solutions displayed: 0
x[1] 1.0
x[3] 1.0
x[5] 1.0
x[6] 1.0
In [21]:
{0: 0.0, 1: 1.0, 2: 0.0, 3: 1.0, 4: 0.0, 5: 1.0, 6: 1.0}
In [22]:
[1, 3, 5, 6]
In [23]:
[(-1, 3, -2)]
In [24]:
{'G': ['G0', 'G1'],
'x_{1}=0': ['x_{1}', 'C_{0}'],
'x_{1}=1': ['x_{1}', 'G1'],
'x_{2}=0': ['x_{2}', 'C_{0}'],
'x_{2}=1': ['x_{2}', 'G1'],
'x_{3}=0': ['x_{3}', 'G1'],
'x_{3}=1': ['x_{3}', 'C_{0}']}
In [25]:
In [26]:
[(-2, -1, -3), (1, -2, -3)]
In [27]:
{'G': ['G0', 'G1', 'G2'],
'x_{1}=0': ['x_{1}', 'C_{0}', 'G1'],
'x_{1}=1': ['x_{1}', 'C_{1}', 'G1'],
'x_{2}=0': ['x_{2}', 'C_{0}', 'C_{1}'],
'x_{2}=1': ['x_{2}', 'G1', 'G2'],
'x_{3}=0': ['x_{3}', 'C_{0}', 'C_{1}'],
'x_{3}=1': ['x_{3}', 'G1', 'G2']}
In [28]:
In [29]:
(['C_{0}', 'C_{1}', 'G0', 'G1', 'G2', 'x_{1}', 'x_{2}', 'x_{3}'],
[{'C_{0}', 'G1', 'x_{1}'},
{'C_{1}', 'G1', 'x_{1}'},
{'C_{0}', 'C_{1}', 'x_{2}'},
{'G1', 'G2', 'x_{2}'},
{'C_{0}', 'C_{1}', 'x_{3}'},
{'G1', 'G2', 'x_{3}'},
{'G0', 'G1', 'G2'}])
In [30]:
# ==========================================================
# = Solver Results =
# ==========================================================
# ----------------------------------------------------------
# Problem Information
# ----------------------------------------------------------
Problem:
- Name: unknown
Lower bound: 12.0
Upper bound: 12.0
Number of objectives: 1
Number of constraints: 5
Number of variables: 6
Number of binary variables: 7
Number of integer variables: 7
Number of nonzeros: 6
Sense: minimize
# ----------------------------------------------------------
# Solver Information
# ----------------------------------------------------------
Solver:
- Status: ok
User time: -1.0
System time: 0.01
Wallclock time: 0.01
Termination condition: optimal
Termination message: Model was solved to optimality (subject to tolerances), and an optimal solution is available.
Statistics:
Branch and bound:
Number of bounded subproblems: 0
Number of created subproblems: 0
Black box:
Number of iterations: 0
Error rc: 0
Time: 0.09695792198181152
# ----------------------------------------------------------
# Solution Information
# ----------------------------------------------------------
Solution:
- number of solutions: 0
number of solutions displayed: 0
x[0] 1.0
x[3] 1.0
x[4] 1.0
x[6] 1.0
In [31]:
[0, 3, 4, 6]
In [32]:
[(-2, -1, -3), (1, -2, -3)]
In [33]:
{'G': ['G0', 'G1', 'G2'],
'x_{1}=0': ['x_{1}', 'C_{0}', 'G1'],
'x_{1}=1': ['x_{1}', 'C_{1}', 'G1'],
'x_{2}=0': ['x_{2}', 'C_{0}', 'C_{1}'],
'x_{2}=1': ['x_{2}', 'G1', 'G2'],
'x_{3}=0': ['x_{3}', 'C_{0}', 'C_{1}'],
'x_{3}=1': ['x_{3}', 'G1', 'G2']}
In [34]:
In [35]:
2 Set Declarations
x_index : Size=1, Index=None, Ordered=Insertion
Key : Dimen : Domain : Size : Members
None : 1 : Any : 7 : {0, 1, 2, 3, 4, 5, 6}
каждый_элемент_покрыт_хотябы_одним_множеством_index : Size=1, Index=None, Ordered=Insertion
Key : Dimen : Domain : Size : Members
None : 1 : Any : 8 : {'C_{0}', 'C_{1}', 'G0', 'G1', 'G2', 'x_{1}', 'x_{2}', 'x_{3}'}
1 Var Declarations
x : Size=7, Index=x_index
Key : Lower : Value : Upper : Fixed : Stale : Domain
0 : 0 : 1.0 : 1 : False : False : Binary
1 : 0 : 0.0 : 1 : False : False : Binary
2 : 0 : 0.0 : 1 : False : False : Binary
3 : 0 : 1.0 : 1 : False : False : Binary
4 : 0 : 1.0 : 1 : False : False : Binary
5 : 0 : 0.0 : 1 : False : False : Binary
6 : 0 : 1.0 : 1 : False : False : Binary
1 Objective Declarations
set_count : Size=1, Index=None, Active=True
Key : Active : Sense : Expression
None : True : minimize : 3*x[0] + 3*x[1] + 3*x[2] + 3*x[3] + 3*x[4] + 3*x[5] + 3*x[6]
1 Constraint Declarations
каждый_элемент_покрыт_хотябы_одним_множеством : Size=8, Index=каждый_элемент_покрыт_хотябы_одним_множеством_index, Active=True
Key : Lower : Body : Upper : Active
C_{0} : 1.0 : x[0] + x[2] + x[4] : +Inf : True
C_{1} : 1.0 : x[1] + x[2] + x[4] : +Inf : True
G0 : 1.0 : x[6] : +Inf : True
G1 : 1.0 : x[0] + x[1] + x[3] + x[5] + x[6] : +Inf : True
G2 : 1.0 : x[3] + x[5] + x[6] : +Inf : True
x_{1} : 1.0 : x[0] + x[1] : +Inf : True
x_{2} : 1.0 : x[2] + x[3] : +Inf : True
x_{3} : 1.0 : x[4] + x[5] : +Inf : True
5 Declarations: x_index x set_count каждый_элемент_покрыт_хотябы_одним_множеством_index каждый_элемент_покрыт_хотябы_одним_множеством
['C_{0}', 'C_{1}', 'G0', 'G1', 'G2', 'x_{1}', 'x_{2}', 'x_{3}']
Генерация теcтов
In [37]:
In [38]:
In [39]:
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
/var/data/cocalc/1d588dae-0d14-422a-88b4-c470ec2c8303/hard-problems-formulations/minimum-exact-cover.ipynb Cell 45 line 4
<a href='vscode-notebook-cell://xn--17-6kce2c.xn--80apqgfe.xn--p1ai/var/data/cocalc/1d588dae-0d14-422a-88b4-c470ec2c8303/hard-problems-formulations/minimum-exact-cover.ipynb#X62sdnNjb2RlLXJlbW90ZQ%3D%3D?line=1'>2</a> for clauses_amount_index in range(2, 20):
<a href='vscode-notebook-cell://xn--17-6kce2c.xn--80apqgfe.xn--p1ai/var/data/cocalc/1d588dae-0d14-422a-88b4-c470ec2c8303/hard-problems-formulations/minimum-exact-cover.ipynb#X62sdnNjb2RlLXJlbW90ZQ%3D%3D?line=2'>3</a> for _ in range(100):
----> <a href='vscode-notebook-cell://xn--17-6kce2c.xn--80apqgfe.xn--p1ai/var/data/cocalc/1d588dae-0d14-422a-88b4-c470ec2c8303/hard-problems-formulations/minimum-exact-cover.ipynb#X62sdnNjb2RlLXJlbW90ZQ%3D%3D?line=3'>4</a> result, got_sets, ilp_model, py3sat_model = generate_tests(clauses_amount_index)
TypeError: cannot unpack non-iterable bool object
In [ ]:
[1, 3, 4, 5, 6]
In [ ]:
In [ ]: